#include<stdio.h>

/*
 *
 * 快速排序：
 * 1. 定下一个基准数，循环该逻辑（小于基准数放左边，大于基准数放右边）。左边--基准数--右边 ：该基准数有序
 * 2. 递归分治
 *
 * before data array: 1 5 7 8 3 5 9 4 1 0
    after data array: 0 1 1 3 4 5 5 7 8 9 
 */

void quicksort(int * data, int start, int end);
int partition(int * data, int left, int right);
int main(){
	int data[] = {1, 5, 7, 8, 3, 5, 9, 4, 1, 0};
	int i = 0;
	int length = sizeof(data) / sizeof(int);
	printf("before data array: ");
	for(i = 0; i < length; i++){
		printf("%d ", data[i]);
	}
	quicksort(data, 0, length - 1);
	
	printf("\nafter data array: ");
	for(i = 0; i < length; i++){
		printf("%d ", data[i]);
	}
}

void quicksort(int * data, int start, int end){
	if(start < end){
		int mid = partition(data, start, end);
		quicksort(data, start, mid-1);
		quicksort(data, mid+1, end);
	}
}

int partition(int * data, int left, int right){
	int tmp = data[left];
	while(left < right){
		while(left < right && data[right] >= tmp){
			right--;
		}
		data[left] = data[right];
		while(left < right && data[left] <= tmp){
			left++;
		}
		data[right] = data[left];
	}
	data[left] = tmp;
	return left;
}
